package com.dyna.algorithm.model.tree;

public class RedBlackTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    
    private class Node {
        K key;
        V value;
        Node left, right, parent;
        boolean color;
        
        Node(K key, V value, boolean color) {
            this.key  = key;
            this.value  = value;
            this.color  = color;
            this.left  = this.right  = this.parent  = nil;
        }
    }
    
    private final Node nil = new Node(null, null, BLACK); // 哨兵节点 
    private Node root = nil;
    
    // 插入操作 
    public void insert(K key, V value) {
        Node newNode = new Node(key, value, RED);
        Node current = nil;
        Node parent = root;
        
        // 标准BST插入 
        while (parent != nil) {
            current = parent;
            int cmp = key.compareTo(parent.key); 
            if (cmp < 0) parent = parent.left; 
            else parent = parent.right; 
        }
        
        newNode.parent  = current;
        if (current == nil) root = newNode;
        else if (key.compareTo(current.key)  < 0) current.left  = newNode;
        else current.right  = newNode;
        
        fixInsert(newNode);
    }
    
    // 插入修复逻辑 
    private void fixInsert(Node node) {
        while (node.parent.color  == RED) {
            Node uncle;
            if (node.parent  == node.parent.parent.left)  {
                uncle = node.parent.parent.right; 
                // Case 1: 叔叔节点是红色 
                if (uncle.color  == RED) {
                    node.parent.color  = BLACK;
                    uncle.color  = BLACK;
                    node.parent.parent.color  = RED;
                    node = node.parent.parent; 
                } else {
                    // Case 2: 当前节点是右子节点 
                    if (node == node.parent.right)  {
                        node = node.parent; 
                        leftRotate(node);
                    }
                    // Case 3: 调整颜色并旋转 
                    node.parent.color  = BLACK;
                    node.parent.parent.color  = RED;
                    rightRotate(node.parent.parent); 
                }
            } else { // 镜像对称情况 
                uncle = node.parent.parent.left; 
                if (uncle.color  == RED) {
                    node.parent.color  = BLACK;
                    uncle.color  = BLACK;
                    node.parent.parent.color  = RED;
                    node = node.parent.parent; 
                } else {
                    if (node == node.parent.left)  {
                        node = node.parent; 
                        rightRotate(node);
                    }
                    node.parent.color  = BLACK;
                    node.parent.parent.color  = RED;
                    leftRotate(node.parent.parent); 
                }
            }
        }
        root.color  = BLACK; // 确保根节点为黑色 
    }
    
    // 左旋操作 
    private void leftRotate(Node x) {
        Node y = x.right; 
        x.right  = y.left; 
        if (y.left  != nil) y.left.parent  = x;
        
        y.parent  = x.parent; 
        if (x.parent  == nil) root = y;
        else if (x == x.parent.left)  x.parent.left  = y;
        else x.parent.right  = y;
        
        y.left  = x;
        x.parent  = y;
    }
    
    // 右旋操作（与左旋对称）
    private void rightRotate(Node y) {
        Node x = y.left; 
        y.left  = x.right; 
        if (x.right  != nil) x.right.parent  = y;
        
        x.parent  = y.parent; 
        if (y.parent  == nil) root = x;
        else if (y == y.parent.left)  y.parent.left  = x;
        else y.parent.right  = x;
        
        x.right  = y;
        y.parent  = x;
    }
    
    // 辅助方法：中序遍历 
    public void inOrderTraversal() {
        inOrder(root);
    }
    
    private void inOrder(Node node) {
        if (node != nil) {
            inOrder(node.left); 
            System.out.println(node.key  + "(" + (node.color  ? "R" : "B") + ")");
            inOrder(node.right); 
        }
    }
}